package 左哥算法.compare.贪心;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Ch01Magic操作 {
    // 请保证arr1无重复值、arr2中无重复值，且arr1和arr2肯定有数字
    public static int maxOps(Integer[] arr1, Integer[] arr2) {
        double sum1 = 0;
        for (int i = 0; i < arr1.length; i++) {
            sum1 += (double) arr1[i];
        }
        double sum2 = 0;
        for (int i = 0; i < arr2.length; i++) {
            sum2 += (double) arr2[i];
        }
        if (avg(sum1, arr1.length) == avg(sum2, arr2.length)) {
            return 0;
        }
        Integer[] arrMore = null;
        Integer[] arrLess = null;
        double sumMore = 0;
        double sumLess = 0;
        if (avg(sum1, arr1.length) > avg(sum2, arr2.length)) {
            arrMore = arr1;
            sumMore = sum1;
            arrLess = arr2;
            sumLess = sum2;
        } else {
            arrMore = arr2;
            sumMore = sum2;
            arrLess = arr1;
            sumLess = sum1;
        }
        Arrays.sort(arrMore);
        HashSet<Integer> setLess = new HashSet<>();
        for (int num : arrLess) {
            setLess.add(num);
        }
        int moreSize = arrMore.length;
        int lessSize = arrLess.length;
        int ops = 0;
        for (int i = 0; i < arrMore.length; i++) {
            double cur = (double) arrMore[i];
            if (cur < avg(sumMore, moreSize) && cur > avg(sumLess, lessSize)
                    && !setLess.contains(arrMore[i])) {
                sumMore -= cur;
                moreSize--;
                sumLess += cur;
                lessSize++;
                setLess.add(arrMore[i]);
                ops++;
            }
        }
        return ops;
    }

    public static double avg(double sum, int size) {
        return sum / (double) (size);
    }

    public static void compare(Function fun){
        int count=1000;
        Random random=new Random();
        while (count-- > 0) {
            Set<Integer> set=new HashSet<>();
            int n = random.nextInt(50) + 1;
            while (set.size()<n){
                set.add(random.nextInt(100));
            }
            Integer[] arr1=new Integer[n];
            set.toArray(arr1);
            set.clear();
            n = random.nextInt(50) + 1;
            while (set.size()<n){
                set.add(random.nextInt(100));
            }
            Integer[] arr2=new Integer[n];
            set.toArray(arr2);
            int fun1 = fun.run(arr1.clone(), arr2.clone());
            int fun2 =maxOps(arr1.clone(), arr2.clone());
            if (fun1!=fun2){
                System.out.println("-----------------");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                System.out.println(fun1);
                System.out.println(fun2);
            }
        }
        System.out.println("ok");
    }

    public interface Function{
        public int run(Integer[] arr1,Integer[] arr2);
    }
}
